'''
计数排序
'''
class Solution:
    def relativeSortArray(self, arr1, arr2):
        if not arr1 or not arr2:
            return []

        length = max(arr1)+1
        frequency = [0] * length

        for item in arr1:
            frequency[item] += 1

        res = []
        for item in arr2:
            res.extend([item] * frequency[item])
            frequency[item] = 0

        for item in range(length):
            if frequency[item] > 0:
                res.extend([item] * frequency[item])

        return res
            


if __name__ == '__main__':
    s = Solution()
    arr1, arr2 = [2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]
    print(s.relativeSortArray(arr1, arr2))
    